1. Field of the Invention
The present invention is directed generally to apparatus and methods for modifying a data field of a frame subsequently to generation of frame headers and more particularly to an improved signature field in which such modification occurs that provides for optimization of frame generation and emission rates in a transmitting instrument and transmission rates through networks.
2. Description of the Related Art
In the monitoring, testing and maintenance of packet switched networks, it is necessary to measure accurately one or more measures of network latency, for example, the time it takes for a packet to traverse the network from its source to its destination. To measure this traversal time, various apparatus and methods have been developed in the prior art that share a basic concept of placing timestamp information into one or more packets to be emitted into the network by a transmitting instrument and extracting such timestamp information from the timestamp-containing packet at a receiving instrument. Instruments that implement this basic concept can obtain various latency measurements of the network and also of associated devices under test within the network.
Typically, timestamp information is obtained from a local clock or counter in the transmitting instrument and written into the packet prior to its emission into the network. When the packet is received at the receiving instrument, timestamp information within the packet can be read and such information compared to received time information obtained from a local clock or counter in the receiving instrument. The difference between the received time information and the timestamp information conceptually reflects a static measure of the network latency between these two instruments or network endpoints at a particular point in time.
However, since many networks, and especially the Internet, are continually carrying at any particular point in time packets for an indeterminate level of communication traffic, network latency measurements accordingly require timestamp-containing packets to be emitted into the network continuously over a period of time, with the current timestamp information written into each packet. Moreover, the rate of emission of the timestamp containing packets into the network in many test procedures for obtaining latency measurements ideally should be as high as possible. Accordingly, network latency data can be developed that has the broadest coverage and meaning in real time network traffic environments.
In addition to timestamp containing packets sent from one endpoint to another, the timestamp containing packets can be emitted from and received at multiple endpoints, and at any of these endpoints any instrument can act as both a transmitting and receiving instrument for itself or for other instruments at other endpoints, such that the acquired latency data may provide a more complete dynamic overview of the network. For example, multiple point-to-point traversal and round trip transit times, latency through a specific node or device under test within the network, and other such parameters, and time variant changes thereto, can be obtained. Various types of test instruments for these endpoint devices are known in the prior art.
One requirement to ensure accuracy of the network latency measurement is that the clock or counter in the transmitting instrument must be synchronized with the corresponding clock or counter in the receiving instrument such that the difference between the time information derived from each instrument provides valid data. It is possible to synchronize the clocks or counters of two endpoint connected devices by operating them in lockstep or by first obtaining a known offset between them. In a network wherein the endpoints for the latency measurement are geographically diverse or wherein multiple endpoints are subject to the latency measurements, real time clocks in the endpoint devices may be synchronized using an accessible time service or network time protocol, as disclosed in Schulnan, U.S. Pat. No. 5,600,632.
Another requirement to ensure accuracy of the network latency measurement is that the timestamp information preferably be obtained concurrently with framing of the packet and as near as possible to the time the frame is emitted into the network. However, the functional specifications for the frame in which timestamp information is to be inserted, including the format and content of the various fields in the frame that are required for compatibility with the networking framework of the network for which latency measurements are being obtained, are generally not amenable to writing the timestamp information so obtained directly into the data field of the frame. As is known, the format and content of these fields are defined by known protocols, generally implemented as protocol layers of a hierarchical protocol stack, that any network connected device must be cognizant of to be able to interpret frames developed by any other network connected device cognizant of the same protocols.
One known technique to insert timestamp information directly into the frame upon its imminent emission into the network is to provide software or a hardware module in the transmitting instrument that is operative to append such information to the encapsulated payload within the data field of the frame as the bit stream of the frame is being emitted into the network concurrently with the calculation of the frame check sequence appended to the end of the frame. At the receiving instrument, the entire data field with the appended information is, however, interpreted as the payload of the encapsulated packet within the frame, which may result in the payload being discarded for reasons as set forth immediately below.
One of the above mentioned protocols provides that the header, which encapsulates this payload, contains a checksum calculated at the transmitting instrument from the byte values of this header and the payload prior to the timestamp information being appended thereto. At the receiving instrument, these byte values of the received header and payload, which now includes the byte values of the timestamp information, are read to compute a verifying checksum. For the received checksum to be valid, thereby signifying that no error occurred in the value of one or more bytes of the received header and payload during transmission through the network, the received checksum must match the verifying checksum. Thus, it can be clearly seen that should the timestamp information be appended as above described, the received checksum and verifying checksum would not match, resulting in the received packet being discarded. Should the timestamp information be added prior to computation of this checksum, the accuracy of the latency measurement is degraded due to the generally indeterminate time required for subsequent processing at lower protocol layers subsequent to the timestamp information being obtained and the emission of the frame into the network.
One solution to the forgoing problem is disclosed in Perches, U.S. Pat. No. 6,252,891 (the Perches reference). As described therein, timestamp information is written into the frame immediately prior to emission of the frame into the network in a protocol neutral manner such that the received checksum is always valid.
In accordance with the methods and apparatus disclosed in the Perches reference, an initial packet is generated in a conventional manner at a particular protocol layer wherein the initial packet includes a network protocol portion and a payload portion. The payload portion contains several predefined fields and predetermined data within all except four of these fields that are initially empty. The four empty fields, which may be collectively referred to as a signature field, are each of a predetermined or reserved byte count. The network protocol portion contains a checksum computed for the initial packet from the data contained in the payload portion and other header information in the network protocol portion. Clearly, the four empty fields do not contribute to the checksum.
The initial packet is then processed by a test instrument that adds both a signature sequence and a transmit signature timestamp of appropriate byte count to their respective, but heretofore empty, predefined fields within the signature field reserved in the payload portion. For each successive frame generated by the test instrument, the signature sequence number is incremented starting with the initial sequence number obtained from the initial packet and the transmit signature timestamp is obtained from a local clock in the packet generator. Otherwise, all other fields in the payload portion and network protocol portion, including the pre-computed checksum, remain unchanged in each successive frame.
In order for the pre-computed checksum as computed in the initial packet to remain unchanged and valid after inclusion of the signature sequence number and transmit signature timestamp that change in each successive frame, the test instrument also adds a one's complement bit-by-bit inverse of the signature sequence number and a one's complement bit-by-bit inverse of the transmit signature timestamp to their respective predefined fields in the signature field. Since the checksum of the signature sequence number and the transmit signature timestamp taken together with their respective inverses is zero, the pre-computed checksum in each successive packet accordingly remains valid irrespective of the insertion of the additional bytes into the signature field.
As taught in the Perches reference the total number of bytes for the one's complement inverse fields is equal to the number of bytes for the signature sequence number and the transmit signature timestamp fields to maintain neutrality of the prior computed checksum. In the particular embodiment disclosed therein, the number of bytes reserved for the signature sequence number is two bytes and the number of bytes reserved for the transmit signature timestamp is four bytes, resulting in the total length for the one's complement inverse fields being six bytes.
However, should it be desirous to increase the number of packets emitted to accommodate a sequence number greater than 216 or to provide a greater resolution of the timestamp, the number of bytes for the respective one of these fields would need to be increased thereby requiring an equal number of bytes to be added to the corresponding one's complement inverse field. Furthermore, should any additional fields be desired in a test procedure, the number of bytes for each one of these additional fields necessarily requires the addition of an equal number of bytes for a corresponding one's complement inverse field. Since packet size and emission rates are inversely related, a need exists that obviates the necessity to include a one's complement inverse field of an equal number of bytes for each field added subsequent to calculation of the prior computer checksum so that emission rates are maintained as high as possible.
Instead of providing an initial packet with a pre-computed checksum as described in the Perches reference, it is also possible to simulate the processing of the payload and its encapsulating header for the packet at the protocol layer at which the checksum is computed, as is known in other test instruments. In such simulation, the payload and header still need to be read in order to compute the checksum prior to any information being written into the signature field. As the timestamp information and any other information is being written into the signature field, the entire frame is read so that a frame check sequence (FCS) can be appended to the frame as it is being emitted by the test instrument. Thus, the requirement that the encapsulated packet first be read to compute the checksum and then the frame be read in its entirety to compute the FCS may further lower the effective rate that such frames can be generated and emitted into the network.
In a packet generator wherein upper layer processing of the payload and encapsulating header is simulated, it would be highly desirable to be able to provide a valid checksum for the header concurrently with the frame being read during computation of the FCS to maximize the rate such frames are generated and emitted. Accordingly, another need exists that obviates the requirement to first read the encapsulated packet to compute the checksum.
After the test instrument emits the frames containing a signature field of the type disclosed in the Perches reference, the receiving test instrument must determine that the signature field is present and valid. Since the signature field has a known format and has been appended to the end of the predefined payload, the receiving instrument can generally presume the position of the signature field. To determine validity, a test may be performed to verify, for example, that the data in the presumed position of the signature sequence number and its inverse are indeed complements of each other, and possibly a further test performed to verify that the same condition is true for the transmit timestamp signature field and its inverse.
Although the signature field is appended as described above to the pre-existing payload, and thus at the end of the data field of the emitted frame, the signature field may not be at precisely the end of the data field when the frame is received at the receiving instrument. Various devices, including devices under test, within the network may remove and rewrite some of the header information in the frame, resulting in a lesser byte count preceding the data field. In order to maintain a minimum required length of the frame, any such device will move the remaining frame data up to fill that void and then pad the end of the frame to maintain the minimum length. For example, Ethernet devices within VLAN networks are an example of such a device under test. The result is that the signature sequence number and its complement and the transmit timestamp signature and its complement may or may not be at their presumed position within the received frame, and must therefore be searched for.
In a signature field that utilizes the sequence/sequence complement and the timestamp/timestamp complement, it can be shown that simply testing for these conditions as a means for identifying the location of the signature field, and thus the transmit timestamp signature and signature sequence number fields, can not be error free. Because of the randomness of the data in the packet, there is a certain probability that the packet bytes just prior to the signature field will be the complement of the signature field, in such a way that a test that assumes that the signature field begins with these packet bytes may indicate a valid sequence/sequence complement and timestamp/timestamp complement, even though that is a false location for the signature field.
Therefore, when network devices move the location of the signature field by a small number of bytes, it is no longer possible to determine at the receiving instrument without some non-zero probability of error exactly where the signature field is. In fact, the likelihood of error is very high if the test instrument emits a sufficient number of frames.
It is therefore highly desirable that the signature field can be accurately located after its position has been shifted by an indeterminate number of bytes. Accordingly, a need exists to provide a signature field in which test conditions are verifiable at a receiving instrument without false results or errors.
It may also be seen in the signature field described in the Perches reference that the data for either the signature sequence number and the transmit timestamp signature, and their respective inverses, may include identical bytes in successive frames. For example, the signature sequence number and its inverse are each described as having a width of two bytes. As the least significant byte of the signature sequence number is incremented for each successive frame, the next higher order byte, as well as its bit-by-bit inverse, will contain the same value for up to a maximum of two hundred fifty six frames. In a similar example for the transmit signature timestamp, and its inverse, it should be noted that the least significant bit may change by more than one in each successive frame resulting in fewer successive frames having higher order bytes for these fields remaining unchanged. However, as described in the Perches reference, the transmit signature timestamp and its inverse each have a length of four bytes so that a theoretical maximum of 224 number of frames wherein the most significant byte remains unchanged could be emitted.
After the frame is emitted into the network, it may traverse a sub-network or link therein in which one or more impermissible byte values cannot appear therein. For example, in a synchronous optical network (SONET), high-level data link control (HDLC) frames, as defined in RFC 2175, each begin and end with a flag sequence represented as 0x7E. Accordingly, a byte value equal to the flag sequence may not appear anywhere within the frame itself After computation of the FCS for each frame, any occurrence of a byte value within the frame that is the same as the flag sequence value is converted to a new value of two bytes, represented as 0x7D ×5E, using a process commonly referred to as byte stuffing. So that no confusion exists upon interpreting the frame upon receipt, a normal byte value of 0x7D occurring within the frame further needs to be stuffed such that a new value of two bytes, represented as 0x7D 0x5D, results. Upon receipt of the HDLC frame, the stuffed bytes are reconstructed to their original value prior to calculating the FCS for the received frame.
When testing networks, it is highly desirable that the minimum allowed size of the frame be used to maximize effective transmission rate of such frames through the network. In a SONET network, the minimum frame size allowed is forty bytes. Therefore, for each byte stuffed in the frame, the effective transmission rate of the frame through the network is reduced to 40/(40+N) of the normal line rate, wherein N is the number of bytes stuffed in each frame.
When a frame contains random data the occurrence of either 0x7D or 0x7E should also be sufficiently random such that the effective transmission rate through the SONET link should not be significantly degraded. However, as set forth above, when one or more byte values of successive frames remain unchanged over many frames, and further when the repeating byte values is subject to byte stuffing, the average transmission rate for all such frames through the network can be significantly lowered from the transmission rate obtainable from transmission of all minimum sized frames. The result is that the test instrument receiving a significant number of byte-stuffed frames is not able to establish a consistent line-rate test that would normally require minimum sized packets.
It is therefore highly desirable that the effects of byte stuffing be minimized. Accordingly, a need exists that randomizes byte values within frames that may otherwise potentially remain unchanged over many frames.